
// 生成随机数组
function randomList(start, end, length) {
    var random_list = []
    for (var i = 0; i < length; i++) {
        random_list.push(Math.random() * (end - start) + start)
    }
    return random_list
}
 

function exchange(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}


// 冒泡排序
function bubbleSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1])
                exchange(arr, j, j + 1);
        }
    }
}


// 堆排序
function heapSort(arr) {
    buildMaxHeap(arr);
    for (var i = arr.length - 1; i >= 1; i--) {
        exchange(arr, 0, i);
        arr.heapSize--;
        maxHeapify(arr, 0);
    }
}


function heapParent(i) {
    return (i - 1) >> 1;
}


function heapLeft(i) {
    return (i << 1) + 1;
}


function heapRight(i) {
    return (i + 1) << 1;
}


// 建最大堆
function buildMaxHeap(arr) {
    arr.heapSize = arr.length;
    for (var i = arr.length >> 1 - 1; i >= 0; i--) {
        maxHeapify(arr, i);
    }
}


// 维护最大堆的性质
function maxHeapify(heap, i) {
    var l = heapLeft(i);
    var r = heapRight(i);
    if (l < heap.heapSize && heap[l] > heap[i]) 
        var largest = l;
    else 
        largest = i;
    if (r < heap.heapSize && heap[r] > heap[largest])
        largest = r;
    if (largest != i) {
        exchange(heap, i, largest);
        maxHeapify(heap, largest);
    }
}


// 快速排序
function quickSort(arr) {
    var stack = [];
    stack.push([arr, 0, arr.length - 1]);
    while (stack.length > 0) {
        var arg = stack.pop();
        arg.push(stack);
        quickSort_.apply(null, arg);
    }
}


function partition(arr, p, r) {
    var x = arr[r];
    i = p - 1;
    for (var j = p; j <= r - 1; j++) {
        if (arr[j] <= x) {
            i++;
            exchange(arr, i, j);
        }
    }
    exchange(arr, i + 1, r);
    return i + 1;
}


function randomized_partition(arr, p, r) {
    var i = parseInt(Math.random() * (r - p + 1) + p);
    exchange(arr, r, i);
    return partition(arr, p, r);
}


function quickSort_(arr, p, r, stack) {
    if (p < r) {
        var q = randomized_partition(arr, p, r);
        stack.push([arr, q + 1, r]);
        stack.push([arr, p, q - 1]);
    }
}


// 比较两个整形数组是否相同
function arrayCompare(arr1, arr2) {
    if (arr1.length != arr2.length)
        return false;
    for (var i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i])
            return false;
    }
    return true;
}


function test(sortMethod, arr, truth) {
    var copy = arr.concat();
    var time1 = new Date();
    sortMethod(copy);
    var time2 = new Date();
    console.assert(arrayCompare(copy, truth));
    return time2 - time1;
}


function main() {
    var methodList = [bubbleSort, heapSort, quickSort];
    var timeList = [];
    var nList = [];
    for (var n = 100; n < 1000; n++) {
        nList.push(n);
        var arr = randomList(0, 1000, n);
        var truth = arr.concat();
        bubbleSort(truth);
        for (var i = 0; i < methodList.length; i++) {
            var time = test(methodList[i], arr, truth);
            if (timeList[i] == undefined)
                timeList[i] = [];
            timeList[i].push(time);
        }
    }
    let board = getBoard()
    let p = new Figure(board)
    p.plot(nList, timeList[0], {color: 'green'})
    p.plot(nList, timeList[1], {color: 'blue'})
    p.plot(nList, timeList[2], {color: 'red'})
}


main();
